package GBP;

import java.util.*;

/**
 * RybGBP.java
 * Created: 2006-01-07 20:30
**/

/**
 * This class performs the Fiduccia-Mattheyses variant of 
 * the Kernighan-Lin algorithm for a graph-bipartitioning-problem.
 *
 * @author T.S.Yo
**/

/**
The Fiduccia-Mattheyses variant of the Kernighan-Lin algorithm:
---------------------------------------------------------------------
Create initial partitioning;
    While cutsize is reduced {
        Unlock all nodes;
        While valid moves exist {
            Use bucket data structures to find unlocked node in each partition that most
            improves cutsize when moved to other partition;
            Move whichever of the two nodes most improves cutsize while not exceeding
            partition size bounds;
            Lock moved node;
            Update nets connected to moved nodes, and nodes connected to these nets;
        } endwhile;
        Backtrack to the point with minimum cutsize in move series just completed;
    } endwhile;
---------------------------------------------------------------------
**/

public class KLFM{
    private GraphDef graph;                       // The reference graph
    private Individual oriInd, newInd;            // The original and new bipartitioning
    private int[] nodeIsFree;                     // To record  if a node is free
    private int[] gainValues;                     // To record  the gain values
    private LinkedList<Integer>[] bucket0, bucket1;        // Buckets to store nodes in order of gain
    private int maxDegree;                        // The max degree in the given graph
    private int maxGain0,maxGain1;                // The max gain for each partition
    private int balance;                          // Flag to record the balance of 2 partitions
    private LinkedList<Individual> candidates;    // Possible candidates for local optimum

//---------------------------------------------------------------------
// Constructor
    /** Given a graph definition and a bipartition solution to initialize **/
    public KLFM(final GraphDef gDef, final Individual ind){
        initKLFM(gDef,ind);
    }
    
//---------------------------------------------------------------------
// Initialization
    /** Initializing the algorithm, used by constructor or recursive call **/
    public void initKLFM(final GraphDef gDef, final Individual ind){
        // Copy from given information
        oriInd = new Individual(ind);             // Copy of given individual (a bipartition solution)
        newInd = new Individual(ind);             //
        int[] oriGenes = copyArray(oriInd.getGenes());  //  Retreive the original partitioning
        graph  = oriInd.getGDef();                // Copy of the given graph

        // Retrieve graph information
        int nNode = graph.graph.length;           // Number of nodes
        maxDegree = findMaxDegree();              // Linear search for max degree

        // Set all nodes free
        nodeIsFree = new int[nNode];              // To record if a node is locked 
        for (int i = 0; i < nNode; i++){          // Set all nodes free
            nodeIsFree[i] = 1;
        }
        
        // Initializae gain-values and buckets
        gainValues = new int[nNode];                // To record the nodes' gain-values 
        bucket0 = new LinkedList[(2*maxDegree+1)];  // Buckets to store nodes in order of gain
        bucket1 = new LinkedList[(2*maxDegree+1)];  //
        for(int i = 0; i < bucket0.length; i++){    // Initialize each LinkedList
            bucket0[i] = new LinkedList<Integer>();
            bucket1[i] = new LinkedList<Integer>();
        }
        // Put all nodes into buckets
        for (int i = 0; i < nNode; i++){            // Put all nodes into buckets
            putBuckets((i+1),oriInd);
        }
        //showBuckets();    // For testing
        
        // Find maxGain
        findMaxGain(oriInd);

        // Check balance
        balance = getBalance(oriGenes);

        // Initialze candidates
        candidates = new LinkedList<Individual>();
        candidates.add(new Individual(oriInd));
    }
    
//---------------------------------------------------------------------
// Running KLFM
    /** Initializing the algorithm, used by constructor or recursive call **/
    public Individual runKLFM(){
        Individual bestInd = new Individual(oriInd); 
        //int counter = 0;    // For testing: KLFM is in linear complexity
        
        // Main loop 
        while(!allNodesLocked(newInd.getGenes())){                 // Check if all nodes are fixed
            // Check balance to decide which node to move
            // Move a node, set it fixed, and re-compute related gains
            
            if(balance > 0){
                move1To0(newInd);
            } else if(balance < 0) {
                move0To1(newInd);
            } else {
                moveMaxGain(newInd);
            }
        
            // Re-calculate balance and maxGain
            balance = getBalance(newInd.getGenes());
            findMaxGain(newInd);
            //System.out.println("  Balance = "+balance);    //For testing
            //System.out.println("  newInd:    "+newInd);    //For testing
            //showArray(gainValues);    // For testing
            //showBuckets();    // For testing

            // Check balance to decide whether to save this solution
            if(balance==0){
                //System.out.println("  Add candidate....");    //For testing
                candidates.add(new Individual(newInd));
            }
            //counter++;
        }
        //System.out.println("  FM counter = "+counter);    //For testing
        //showArray(nodeIsFree);    //For testing : to see if all nodes fixed
        
        // Search the best individual through candidates
        //System.out.println("  Looking for best solution....");    //For testing
        int bestFitness = oriInd.getFitness();
        for(int i = 0; i < candidates.size(); i++){
            if(candidates.get(i).getFitness() > bestFitness){
                bestInd.setGenes(candidates.get(i).getGenes());
                bestFitness = bestInd.getFitness();
                //System.out.println("  Better solution found: "+i+" fitness: "+bestFitness);    //For testing
            }
        }
        
        // Return the best Individual
        return bestInd;
    }
        
//---------------------------------------------------------------------
// Moving nodes
    /** Move one node from partition 1 to partition 0 **/
    public void move1To0(final Individual ind){
        // Initialize working array
        int[] tmpGenes = copyArray(ind.getGenes());
        
        // Retrieve the node with maxGain in partition 1
        int bIndex = maxDegree - maxGain1;        // Get index: 0 if maxGain=maxDegree
        int nodeId = bucket1[bIndex].remove();    // Get and remove the first nodeId
        while(nodeIsFree[(nodeId-1)]==0){
            bucket1[bIndex].add(nodeId);          // If the node is not free, put it back
            nodeId = bucket1[bIndex].remove();    //   , and then get next node
        }
        //System.out.println("Move node "+nodeId+" from 1 to 0");  // For testing
        
        // Flip the partion
        tmpGenes[nodeId-1] = 0;                   // Flip the partition
        ind.setGenes(tmpGenes);                   // Record the flip into newInd
        
        // Set node as fixed
        nodeIsFree[nodeId-1] = 0;
        
        // Put the node back to buckets
        putBuckets(nodeId,ind);
        
        // Recompute the gain -valuesof linked nodes
        int[] nb = graph.graph[nodeId-1].getNeighbors();
        for(int i = 0; i < graph.graph[nodeId-1].getNumNeighbors();i++){
            removeFromBuckets(nb[i],ind);
            putBuckets(nb[i],ind);
        }
    }

    /** Move one node from partition 0 to partition 1 **/
    public void move0To1(final Individual ind){
        // Initialize working array
        int[] tmpGenes = copyArray(ind.getGenes());
        
        // Retrieve the node with maxGain in partition 0
        int bIndex = maxDegree - maxGain0;        // Get index: 0 if maxGain=maxDegree
        int nodeId = bucket0[bIndex].remove();    // Get and remove the first nodeId
        while(nodeIsFree[(nodeId-1)]==0){
            bucket0[bIndex].add(nodeId);          // If the node is not free, put it back
            nodeId = bucket0[bIndex].remove();    //   , and then get next node
        }
        //System.out.println("Move node "+nodeId+" from 0 to 1");  // For testing
        
        // Flip the partion
        tmpGenes[nodeId-1] = 1;                   // Flip the partition
        ind.setGenes(tmpGenes);                   // Record the flip into newInd
        
        // Set node as fixed
        nodeIsFree[nodeId-1] = 0;
        
        // Put the node back to buckets
        putBuckets(nodeId,ind);
        
        // Recompute the gain -valuesof linked nodes
        int[] nb = graph.graph[nodeId-1].getNeighbors();
        for(int i = 0; i < graph.graph[nodeId-1].getNumNeighbors();i++){
            removeFromBuckets(nb[i],ind);
            putBuckets(nb[i],ind);
        }
    }

    /** Move the node with maximum gain **/
    public void moveMaxGain(final Individual ind){
        if(maxGain1 > maxGain0){
            move1To0(ind);
        } else {
            move0To1(ind);
        }
    }

//---------------------------------------------------------------------
// Sub-functions for main algorithm
    /** Put a node into buckets, also update the gain-values
        This method only modify gainValues, bucket0 and bucket1 **/ 
    public void putBuckets(final int nodeId, final Individual curInd){
        int i = nodeId - 1;
        int[] tmpGenes = copyArray(curInd.getGenes());
        
        // Compute the gain
        int gain = getGain(i, curInd);            // Gain = increased fitness
        gainValues[i] = gain;                     // Update the gain-values
        //System.out.println("Node: "+nodeId+" gain = "+gain);    // For testing
            
        // Store the node into bucket
        // Index of buckets: -maxDegree ~ +maxDegree, smaller bucketIndex -> higher gain
        int bucketIndex = maxDegree - gain;       
        //System.out.println(" Put node "+nodeId+" into bucket "+tmpGenes[i]);    // For testing
        //System.out.println(" with gain = "+gain+", bucketIndex = "+bucketIndex);  // For testing
        
        if(tmpGenes[i]==0){
            bucket0[bucketIndex].add(new Integer(nodeId));
        } else if(tmpGenes[i]==1){
            bucket1[bucketIndex].add(new Integer(nodeId));
        } else {
            System.out.println("    !!!     Unexpected partition, niether 0 nor 1    !!!!");
        }
    }

    /** Remove a node from buckets 
        This method only modify bucket0 and bucket1 **/ 
    public void removeFromBuckets(final int nodeId, final Individual curInd){
        int i = nodeId - 1;
        
        // Find the node (which buckets, which gain-value)
        int bucket = curInd.getGenes()[i];        // Which bucket
        int listIdx = maxDegree - gainValues[i];  // Which LinkedList
        int nodeIdx = 0;                          // Which element
        int tmp = 0;                              // For retreiving nodes from the LinkedList
        //System.out.println(" Removing "+nodeId+"  ,element at bucket"+bucket+"["+listIdx+"]");    // For testing
        
        switch(bucket){
            case 0:                               // The enighbor node is in bucket0
                nodeIdx = bucket0[listIdx].indexOf(nodeId);
                //System.out.println(" Removing "+nodeId+"  ,element at bucket0["+listIdx+"]["+nodeIdx+"] : " );    // For testing
                tmp = bucket0[listIdx].remove(nodeIdx);
                //System.out.println(" Removing "+nodeId+"  ,element at bucket0["+listIdx+"]["+nodeIdx+"] : "+tmp );    // For testing
                break;
            case 1:                               // The enighbor node is in bucket1
                nodeIdx = bucket1[listIdx].indexOf(nodeId);
                //System.out.println(" Removing "+nodeId+"  ,element at bucket0["+listIdx+"]["+nodeIdx+"] : ");    // For testing
                tmp = bucket1[listIdx].remove(nodeIdx);
                //System.out.println(" Removing "+nodeId+"  ,element at bucket1["+listIdx+"]["+nodeIdx+"] : "+tmp );    // For testing
                break;
            default:                           
                System.out.println("    !!!     Unexpected partition, niether 0 nor 1    !!!!");
                break;
        }
    }

    /** Calculate the gain **/ 
	private int getGain( final int index, final Individual curInd ) {
        Individual tmpInd = new Individual(curInd);
        int[] tmpGenes = copyArray(tmpInd.getGenes());
        tmpGenes[index] = flipNode(tmpGenes[index]);          // Flip the group of the specified node
        tmpInd.setGenes(tmpGenes);                            // Set the new group to a temp individual
        int gain = tmpInd.getFitness() - curInd.getFitness(); // Gain = increased fitness
        return gain;
	}

    /** Return the value of the other partition: 0 -> 1 or 1 -> 0**/ 
    private int flipNode(int group){
        return (-1*group+1);
    }

    /** Calculate MaxGain for both partitions **/ 
    private void findMaxGain(final Individual ind){
        int nNode = graph.graph.length;           // Number of nodes
        int[] tmpGenes = ind.getGenes();
        maxGain0 = -1*maxDegree;
        maxGain1 = -1*maxDegree;
        
        for(int i = 0; i < nNode; i++){
            switch(tmpGenes[i]){
                case 0:
                    if ((gainValues[i] > maxGain0)&&(nodeIsFree[i]==1)){
                        maxGain0 = gainValues[i];
                    } 
                    break;
                case 1:
                    if ((gainValues[i] > maxGain1)&&(nodeIsFree[i]==1)){
                        maxGain1 = gainValues[i];
                    }
                    break;
                default:
                    System.out.println("    !!!!    Wrong partition index    !!!!");
                    break;
            }
        }
        //System.out.println("maxGain0 = "+maxGain0+"    maxGain1 = "+maxGain1);     // For testing
    }

    /** Return the balance of a given partitioning: 
        >0 : partition '1' have more nodes   
        <0 : partition '0' have more nodes   
        =0 : balanced                               **/
    private int getBalance(final int[] curPart){
        int bal = 0 - (curPart.length/2);         // Start from -1*(half of nodes)
        for(int i = 0; i < curPart.length; i++){
            bal+=curPart[i];                      // Add # of partition '1'
        }
        //System.out.println("    Balance = "+bal);     // For testing
        return bal;
    }

    /** Return if all nodes in one(or both) partition are locked **/
    private boolean allNodesLocked(final int[] curPart){
        int sum0 = 0;
        for(int i = 0; i < nodeIsFree.length; i++){
            sum0 += nodeIsFree[i];               // Add up all free(non-zero) nodes
        }
        //System.out.println("All nodes are locked: "+(sum0 == 0));     // For testing
        return ((sum0 == 0));
    }
//---------------------------------------------------------------------
// Miscellaneous sub-functions
    /** Copy an integer array by values **/ 
	private int [] copyArray( int [] source ) {
		int [] result = new int[ source.length ];
		for( int i = 0; i < result.length; i++ )
			result[ i ] = source[ i ];
		return result;
	}

    /** Linear search for max degree in the given graph **/ 
    private int findMaxDegree(){
        int maxDegree = 0;                              // Linear search for max degree
        for (int i = 0; i < graph.graph.length; i++){
            int nNeighbors = graph.graph[i].getNumNeighbors();
            if(nNeighbors > maxDegree){
                maxDegree = nNeighbors;
            }
        }
        //System.out.println("MaxDegree = "+maxDegree);    // For testing
        return maxDegree;
    }
    
    /** Show the arrays of LinkedList, bucket0 and bucket1 **/
    public void showBuckets(){
        // Index of buckets: -maxDegree ~ +maxDegree
        // Bucket0
        System.out.println("Index        Bucket0");
        System.out.println("----------------------------------------");
        for(int i = 0; i < bucket0.length; i++){
            System.out.print("\n"+(-1*(i-maxDegree))+"        ");
            for(int j = 0; j < bucket0[i].size(); j++){
                System.out.print("  "+(bucket0[i].get(j)));
            }
            System.out.println("");
        }
        System.out.println("");
        System.out.println("");
        // Bucket1
        System.out.println("Index        Bucket1");
        System.out.println("----------------------------------------");
        for(int i = 0; i < bucket1.length; i++){
            System.out.print("\n"+(-1*(i-maxDegree))+"        ");
            for(int j = 0; j < bucket1[i].size(); j++){
                System.out.print("  "+(bucket1[i].get(j)));
            }
            System.out.println("");
        }
    }

    /** Show the gain-values **/
    public void showArray(int[] a){
        String output = "Array Values: \n";
        for(int i = 0; i < a.length; i++){
           output = output + " " + a[i];
           if((i%25)==24) output = output + "\n";
        }
        System.out.println(output);
    }
    
}